package done.easy_401_500;

import org.junit.Test;

import java.util.*;

import static com.study.util.LogUtil.info;

/**
 * 448. Find All Numbers Disappeared in an Array 找到所有数组中消失的数字
 * <p>
 * 给定一个范围在  1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，
 * 数组中的元素一些出现了两次，另一些只出现一次。找到所有在 [1, n]
 * 范围之间没有出现在数组中的数字。
 * <p>
 * 示例:
 * 输入: [4, 3, 2, 7, 8, 2, 3, 1]
 * 输出: [5, 6]
 * <p>
 * 2019-04-14 5:01 PM
 **/
@SuppressWarnings("all")
public class FindAllNumbersDisappearedInAnArray {

    public List<Integer> findDisappearedNumbers(int[] nums) {
        // 190414 first
        return null;
    }

    @Test
    public void test() {
        info("[5, 6] -> {}",
                findDisappearedNumbers(new int[]{4, 3, 2, 7, 8, 2, 3, 1}));
    }
}




























/*
// 方法一
public List<Integer> findDisappearedNumbers(int[] nums) {
    List<Integer> array = new ArrayList<>();

    // 用一个数组专门记录，每一个数字是否存在
    boolean[] find = new boolean[nums.length + 1];

    for (int i = 0;i < nums.length; i++)
        find[nums[i]] = true;

    // find 里面藏着一个 0 所以要从 1 开始
    for (int i = 1; i < find.length; i++)
        if (find[i] == false)
            array.add(i);

    return array;
}
*/

/*
// 方法二
public List<Integer> findDisappearedNumbers(int[] nums) {
    // 凡是出现过的数字，考虑到都是正数。
    // 出现过的数字把他们转化成下标并将下标对应的内容最高位置1
    // 在遍历一次数组，那么没出现过的数字的对应得下标则为正数，其他为负数
    // （或者也可以直接判断最高位是不是1）
    List<Integer> res = new ArrayList<>();

    for(int i = 0; i < nums.length; i++)
        nums[(nums[i]&0x7fffffff)-1] |= 0x80000000;

    for(int i = 0; i < nums.length; i++)
        if(nums[i] > 0) res.add(i+1);

    return res;
}
*/
